/**
 * @author ZhengDp
 * @Date 2023/4/25 12:22
 */
public class 二分查找 {

    /*
    * #problem 69 x的平方根
    * */
    // 1. 二分查找
    public int mySqrt(int x) {
        int left = 0,right = x+1;
        int ans = 0;
        while(left < right ) {
            int mid = (right-left)>>1 + left;
            long res = mid * mid;
            // k^2 <= k ==> 找k的最大值（搜索右侧边界）
            if(res <= (long)x) {
                ans = mid;
                // 收缩左侧边界
                left = mid+1;
            }  else if(res > (long) x) {
                right = mid;
            }
        }
        return ans;
    }

    /*
    * #problem 367 有效的完全平方数
    * */
    // 1. 二分查找
    public boolean isPerfectSquare(int num) {
        int left = 1,right = num;
        while(left <= right) {
            int mid = (right-left)/2 + left;
            if((long)mid*mid == num) {
                return true;
            } else if((long)mid*mid < num) {
                left = mid+1;
            } else {
                right = mid-1;
            }
        }

        return false;
    }

    /*
    * #problem 33 搜索旋转排序数组
    * */
    // 1. 二分，区间缩小时有额外的条件
    public int search(int[] nums, int target) {
        int left = 0,right = nums.length-1;
        while(left <= right) {
            int mid = (right-left)/2 + left;
            if(nums[mid] == target) {
                return mid;

            }
            // left ~ mid : 有序
            else if(nums[left] <= nums[mid]) {
                if(nums[mid] > target && nums[left] <= target) {
                    right = mid-1;
                } else {
                    left = mid+1;
                }
            }
            // left ~ mid : 非单调递增 ==> [x..mid..right] ==> 单调递增 ==> mid ~ right : 有序
            else {
                if(nums[mid] < target && nums[right] >= target) {
                    left = mid+1;
                } else {
                    right = mid-1;
                }
            }
        }
        return -1;

    }

    /*
    * #problem 74 搜索二维矩阵
    * */
    // 1. 二分查找 --> 升序矩阵，将二维转换为一维即可
    public boolean searchMatrix(int[][] matrix, int target) {
        int n = matrix.length,m = matrix[0].length;
        int left = 0,right = n*m-1;
        while(left <= right) {
            int mid = (right-left)/2 + left;
            int x = mid/m;
            int y = mid%m;
            if(matrix[x][y] == target) {
                return true;
            } else if(matrix[x][y] < target) {
                left = mid+1;
            } else {
                right = mid-1;
            }
        }
        return false;
    }

    /*
    * #problem 153 寻找旋转排序数组中的最小值
    * */
    // 1. 二分查找 假设最小值为min,数组的最后一个元素为x
    // 那么有  min 右侧的所有元素都 < x ，min左侧的所有元素都 >x
    /*
    * 我们需要锁定 min  ==> 当nums[mid] < x 时，说明 Mid位于 min的右侧，我们要锁定min，就抛弃mid的右区间
    * 当 nums[mid] > x 时，说明Mid位于min的左侧，锁定min位于mid的右侧，抛弃mid的左区间
    * 不断缩小区间范围，最终left == right时，left指向的值就是 min
    * */
    public int findMin(int[] nums) {
        int left = 0,right = nums.length-1;
        while(left < right) {
            int mid = (right + left) /2;
            if(nums[mid] < nums[right]) {
                right = mid;
            } else {
                left = mid+1;
            }
        }
        return nums[left];
    }
}
